package demo.practice.back;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class P51 {


    public static void main(String[] args) {
        P51 p51= new P51();
        p51.solveNQueens(4);
    }
    private int maxrow;
    private List<List<String>> res;

    public List<List<String>> solveNQueens(int n) {
        maxrow = n;
        res = new ArrayList<List<String>>();
        dfs(0,new LinkedList<>());
        return res;
    }

    private void dfs(int row, LinkedList<Integer> path) {

        if (row == maxrow) {
            //找到了答案
            List<String> r1= new ArrayList<>();
            for(int i=0;i<path.size();i++){
                StringBuffer sb= new StringBuffer();
                for(int j=0;j<maxrow;j++){
                    if(j==path.get(i)){
                        sb.append("Q");
                    }else{
                        sb.append(".");
                    }
                }
                r1.add(sb.toString());
            }
            res.add(r1);
        }

        for (int i = 0; i < maxrow; i++) {
            if (check(path, row, i)) {
                path.add(i);
                dfs(row + 1, path);
                path.removeLast();//其他行时，需要回退一下
            }
        }
    }


    private boolean check(List<Integer> path, int row, int col) {
        for(int i=0;i<row;i++){
            //row1=i  col1= path.get(i)
            //row,col
            // Math.abs(  row1-row )=   Math.abs(  col1-col ) 判断斜线
            if(path.get(i)==col || Math.abs(i- row )== Math.abs(path.get(i)- col )) {
                return false;
            }
        }
        return true;
    }

}
